﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0082_LetterCombinations : IAlgorithm
    {
        // 17. 电话号码的字母组合

        // 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
        // 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
        // 7 9 为4个字母 其他的为3个

        // 提示：
        //  0 <= digits.length <= 4
        //  digits[i] 是范围['2', '9'] 的一个数字。

        public void Test()
        {
            // 算法参数定义
            var digits = "23";
            // 算法执行与打印
            foreach (var item in LetterCombinations(digits))
            {
                Console.Write(item + " ");
            }
        }

        // 算法
        public IList<string> LetterCombinations(string digits)
        {
            var res = new List<string>();
            if (string.IsNullOrEmpty(digits))
                return res;
            Backtrack(digits, new List<char>(), 0, res);
            return res;
        }
        private void Backtrack(string digits,List<char> temp,int i, List<string> res)
        {
            if (temp.Count == digits.Length)
                res.Add(new string(temp.ToArray()));
            else
            {
                var digit = int.Parse(digits[i].ToString());
                var startChar = GetStartCharByDigit(digit);
                var charLength = digit == 7 || digit == 9 ? 4 : 3;
                for (int j = 0; j < charLength; j++)
                {
                    temp.Add((char)(startChar + j));
                    Backtrack(digits, temp, i + 1, res);
                    temp.RemoveAt(temp.Count - 1);
                }
            }
        }
        private char GetStartCharByDigit(int digit)
        {
            var res = 'a' + (digit - 2) * 3;
            if (digit > 7)
                res += 1;
            return (char)res;
        }
    }
}
